'''
	堆排序
	时间复杂度：O(nlog2(n))
	空间复杂度：O(1)
	稳定性：不稳定
	基本思想：如果构造的是最大堆，排序后的结果是从小到大；如果构造的是最小堆，排序后的结果是从大到小
		1. 构造最大堆（最小堆）
			1.1 从最后一个非叶子节点开始，即n/2向下取正
			1.2 找出左节点和右节点，分别与父节点进行比较，如果大，就与父节点进行交换，并记录最大节点的位置
			1.3 如果进行了调整，其子堆也要进行比较调整，即递归子堆
		2. 堆排序
			2.1 将最大堆的A[0]与A[n-1]交换
			2.3 heap_size - 1
			2.4 将剩下的元素进行堆化
			2.5 重复步骤1，2，3直到i<=0
'''
from tool import arr, swp
# 对给定的节点及其子节点进行堆化
# arr:待堆化的数组   i:从第i个元素开始堆化  heap_size:还有多少个堆元素存放在数组中
def max_heapify(arr, i, heap_size):
	l = 2 * i + 1
	r = 2 * i + 2
	# print("i:%d,l:%d,r:%d,n:%d" % (i,l,r,heap_size))
	if l < heap_size and arr[l] > arr[i]:
		largest = l
	else:
		largest = i
	if r < heap_size and arr[r] > arr[largest]:
		largest = r
	if largest != i:
		swp(arr, i, largest)
		max_heapify(arr, largest, heap_size)

# 构建最大堆
def build_max_heap(arr):
	i = len(arr) // 2 - 1
	heap_size = len(arr)
	while i >=0:
		max_heapify(arr, i, heap_size)
		i -= 1
	return arr

# 堆排序
def heap_sort(arr):
	build_max_heap(arr)
	print(arr)
	i = len(arr) - 1
	heap_size = len(arr)
	while i > 0:
		swp(arr, 0, i)
		heap_size = heap_size - 1
		max_heapify(arr, 0, heap_size)
		i = i - 1
	return arr

if __name__ == '__main__':
	arr = heap_sort(arr)
	print(arr)



